package sort.yht;

import sort.util.MySort;

/**
 * 功能描述：插入排序
 *
 * @Author: yht
 * @Date: 2021/8/11 14:12
 */
public class ChaRu implements MySort {

  @Override
  public String getName() {
    return "【插入排序】";
  }

  @Override
  public int[] sort(int[] a) {
//    return cha(a);
    return cha2(a);//最优插入排序
//    return myCha(a);
  }

  private int[] cha(int[] ins) {
    for(int i=1; i<ins.length; i++){
      for(int j=i; j>0; j--){
        if(ins[j]<ins[j-1]){
          int temp = ins[j-1];
          ins[j-1] = ins[j];
          ins[j] = temp;
        }
      }
    }
    return ins;
  }

  private int[] cha2(int[] ins) {
    for(int i=1; i<ins.length; i++){
      int temp = ins[i];//保存每次需要插入的那个数
      int j;
      for(j=i; j>0&&ins[j-1]>temp; j--){//这个较上面有一定的优化
        ins[j] = ins[j-1];//吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
      }
      ins[j] = temp;//将需要插入的数放入这个位置
    }
    return ins;
  }

  private int[] myCha(int[] a) {
    int size = a.length;
    for(int i = 1 ; i < size; i++) {
      for(int j = 0 ; j <= i ; j++) {
        if(a[i] < a[j]){
          int tmp = a[j];
          a[j] = a[i];
          for(int k = i; k > j+1; k--){
            a[k] = a[k-1];
          }
          a[j+1] = tmp;
          break;
        }
      }
    }
    return a;
  }

  public static void main(String[] args) {
    new ChaRu().testAll();
  }
}
